% se2-design.tex


% declare this document to be of class uw-wkrpt (variant se)
%\documentclass[se,legalpaper]{uw-wkrpt}
\documentclass[final]{se2-design}
\usepackage{times}
\usepackage{ifthen}
% we need a glossary
%\usepackage{glosstex}

% we want to be able to use graphics, so import them
\usepackage{graphicx}
\usepackage{wrapfig}

\urlstyle{rm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% set up some variables to make life easier
\newcommand{\tm}{\texttrademark}

\newcommand{\todo}[1]{\textbf{#1}}

% subsubsubsection stuff
\usepackage{subsections}
\setcounter{secnumdepth}{5}
\setcounter{tocdepth}{5}

\usepackage{multirow}

\usepackage{chngcntr}
\usepackage{setspace}
\counterwithin{figure}{section}



% and begin
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% setup the document
\title{Assignment 3: Distributed File System \\Design Document}
\group{11}
%\member{Full name}    {Student#}{email user}{email domain}
\member{Yanna Kang}    {20146835}{yanna.kang}{gmail.com}
\member{Colin Rhodes}  {20130560}   {cprhodes}{uwaterloo.ca}
\member{Charles Dang}  {20128568} {c3dang}{uwaterloo.ca}
\member{Eric Allen}    {20125887}   {eaallen}{uwaterloo.ca}
\school{University of Waterloo}
\faculty{Faculty of Engineering}
\program{ECE454}
\term{S07}
%\date{May 8, 2007}
\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagenumbering{roman}
\tableofcontents
%TODO: Add list of figures/tables back if we need it
\listoffigures
%\listoftables

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% body
\mainmatter{}



\section{Overview}\label{sec:overview}

This section will provide an overview of the design of our Distributed File System. There
are some key reasonable environmental assumptions that we made before beginning design. Firstly,
we are designing the system to be used in a corporate or institutional network of limited
size. The system is not designed to work on the scale of the internet. Secondly, we assume
that the distributed system will be intended to form part of an infrastructure and run continuously,
in contrast to being started for retrieving a single file and then stopped again thereafter.

\subsection{Network Architecture}\label{sec:architecture}
We decided to implement a peer-to-peer solution. We thought this would be an interesting challenge.

To our understanding, there are two `hard' problems in designing peer-to-peer files systems:
maintaining the network and discovering content on the network.
We decided to address these concerns with a solution inspired by a production peer-to-peer
network maintained by a former co-op employer of two of our group members, NeoEdge Networks Inc.
This solution calls for the peer network to be maintained and controlled by a central server.
This control server keeps a record of all content, the active peers in the network, and which peers have
what content pieces. To join the network, a peer simply contacts a control server. To find, upload, or
delete content, a peer contacts the control server for help locating other peers.

One of the problems introduced by using a central server to control the peer network is that this
control server becomes a single point of failure for the network. To solve this problem, our solution will mandate
that two or more control servers will work together to maintain the network such that the failure of any
single server will not cause the failure of the network.

A diagrammatic overview of the network architecture is presented in figure \ref{fig:fantasy}. The details of this diagram
will be explained in the following sections.

\begin{figure}
  \begin{centering}
  \includegraphics[width=1.0\textwidth]{fantasy.png}
  \caption{Network Architecture.}
  \label{fig:fantasy}
  \end{centering}
\end{figure}

\subsection{Content}\label{sec:content}
One of the decisions we had to make in our design was where and how content will be stored in the network.
In our solution, there were two choices for content location: storing content on the peers or storing content
on the control servers. We decided it would allow us to be more flexible to store content on the peers. This design decision gives
us more choices in terms of multiple sources for content and reduces the load on the control servers, presumably
reducing the potential of the central server acting as a bottleneck for the system.

A second decision regarding the design was the representation of the distributed file system -- would it simply be a collection
of files or would it have a directory structure similar to traditional file systems? We decided that a distributed
file system would be more useful if it had a directory structure; however, we wanted to be able to store content
on the peers without having to worry about this structure. For example, if a file X is located in directory Y in
the distributed file system, we don't want to store file X in any particular directory for it to be accessible or
recognized as file X. Our solution to this is to rename each file when it is stored within the distributed system
to the file's hash value (a value generated based on the contents of the file). Using this method we can store all
of a peer's content within a single directory and simply use meta-data to create the illusion of the files residing
within directories. Our system will impose similar `same-name' file restrictions as traditional file systems; that is,
no two files within a single directory in the artificial file system will be allowed to have the same name.

\subsection{Servers}
The distributed file system will be maintained on a set of two or more physical computers
running our server software. Each server will have a role to play in load balancing and fault
tolerance. A single replicated state for the distributed file system will be maintained across all servers.
This replication will be performed so that failover can occur without any loss of information.
This state information will include at least a list of what files are in the system and where they are
located in the directory structure. State information will be persisted in a transactional database protected by a RAID storage.
For the purposes of load balancing, each server may maintain slightly different information about the
structure of network; the connected peers and the content of each peer. This would allow
each server to provide service to a subset of peers from the total network, improving the service that each individual
peer receives, compared with one server controlling the entire network.

The locations of servers will be configured manually be the system administrator and these locations will
be statically provided to both clients and servers. Servers will use this information to coordinate load-balancing and failover activities; peers will use the information to join the network and request service. Part of the load-balancing functionality of the servers will be forcing a peer to attempt to connect to another server if the current server is too busy.

A safeguard built into the failover system is a server's mechanism to refuse service to
a peer. Although this safeguard is initially counter-intuitive to the idea of failover, it is essential to
prevent a potential cascade effect caused by the crash of a single server. If a single server fails
and all of its peers attempt to simultaneously connect to a specific second server, the second server
may be overwhelmed by the increased traffic and suffer a failure. All the peers the second server was servicing in addition to the
peers from the first server may consequently attempt to connect to a third server, and so on, until the system becomes
unusable. If the second server can refuse service to some of the peers that had originally
been connected to the first server, the second failure may be prevented and the system can remain
functional.

Figure \ref{fig:fantasy} presents an overview of the network architecture. Note that the large ellipsis
are meant to indicate that any number of control servers may be present in the network. Note also that
peers connected to different servers are able to share content. This capability will be part of the synchronization
mechanism and will be used if the content cannot be found at a peer connected to the same server as the
requesting peer.

\subsection{Peers}

While the coordination of the network is performed by the control servers, it is the peers that perform
the actual work of storing and delivering files in our distributed file system. Each peer maintains a local
store of some of the content in the system. The size of this local store will be configurable on a peer-by-peer
basis. When the peer downloads a file from the system, this file is
added to its local store. By doing so, content that is in high-demand will have more sources.
If the local store is full when a peer downloads a file, some content will need to be deleted from the
store to make room for this new content. Additionally,
the system will attempt to guarantee that at least two peers in the system have any one piece of content.
This will provide some safeguard against content becoming unavailable if any single peer leaves the network.
This two-or-more peer replication will need to be coordinated by the server and will be based on two criteria:
the available bandwidth and available space in the local store of a potential receiving peer. By replicating
the content on peers with high bandwidth the overall performance of the system will be improved. By avoiding
pushing content to peers with full local stores, unless no peer can be found with a non-full local store,
the content replication mechanism will avoid increasing the availability of one piece of content at the
expense of the availability of another. When a peer attempts to download a file, it will attempt to connect
to peers in order of available bandwidth, as provided by the server, in order to minimize file transfer time.
To prevent overwhelming a single peer, a peer will have the ability to refuse service to requests from other
peers.

In order to ensure that content doesn't disappear from the network a restriction must be placed on what
content can be deleted from a peer's local content store. It is important that if the peer holds the only
copy of any piece of content that it not be deleted to make room for any new content. One peer being the only
peer with a given piece of content could happen in a case where all other peers that had copies of
the content left the network. To prevent this from happening, the peer must ask the server for permission before
deleting any content, and either replicate the content on another peer before downloading the new content
or choose another piece of content to replace to make room.

If the server provides a peer with several peers that have content the peers wants, the peer
may request small parts of the content from each peer. The peer can then assemble the content and
use its hash value to determine correctness. This will help increase transfer performance if the
downloading peer has high-bandwidth availability and the uploading peers have low-bandwidth availability.

\subsection{Interfaces}
There are four conceptual interfaces in our system: Server-To-Server, Peer-To-Server, Server-To-Peer, and Peer-To-Peer.

The Server-To-Server interface is provided between servers for synchronization of state.
A server will be able to poll for the state information of another server. Periodically, the servers will
synchronize with one another for state replication. In the event that a given server is in a non functioning state,
another server will be able to process requests on its behalf.

The Peer-To-Server interface enables the peer to server interactions. A client is able to inform the server that it
is joining or leaving the network. In addition, the client can add content to and delete content from the network.
It may also inform the server what content it has available. When a client asks the server for a particular file,
the client will receive a list of the available peers with the content.

The Server-To-Peer interface allows the server to push information to the peer. This informs
the peer of new network states and of added or removed content.

The Peer-To-Peer interface allows peers to connect to one another to request content.

\section{System User Interface}

The system's user interface will be graphical. The user of each peer application will be able to
view the current contents of the distributed file system and download files from the network.
The interface will provide file searching capabilities and graphical file navigation.
Advanced searching and filtering capabilities will accommodate further ease of access.
The user may download content to any location on their local file system. In the background, the peer
application will fetch the content from the network, make a copy in the local store, then save the content
to the user's chosen location. As mentioned in section \ref{sec:content}, files will be renamed using their
hash values when they are stored in the system to avoid same-name problems. The only name restriction
in the system will be to prevent a user from placing two files of the same name within the same directory
of the distributed file system. The local content store directory used by the peer will be configurable by the user.
In addition, the user may impose a cap on the maximum amount of space the local content store may occupy.
When downloading new content would breach this limit, the peer application must remove files from this store before adding any additional content to the store. If the content is too large to fit in the store, the peer application will
ask the user to enlarge the store and try again. Since file download will not be instantaneous,
the system interface will show download progress, show the estimated time remaining, and provide the ability
for the user to cancel a download. A mockup of the system interface is presented in figure \ref{fig:gui}.

\begin{figure}
  \begin{centering}
  \includegraphics[width=1.0\textwidth]{gui.png}
  \caption{Mockup of the System Interface.}
  \label{fig:gui}
  \end{centering}
\end{figure}

\section{Error Handling}

Fault-tolerance was a key design consideration of our system. Specifically, the failure of any
single element cannot cause the total failure of the system. State replication between the servers enables
the peers to seamlessly transition in the event of failure. The failover mechanism will usually be transparent
to the user. Although the failure of a single component in the network cannot cause total failure, a partial failure
condition is possible. This would result from failover servers refusing to provide service to disconnected peers
in order to protect themselves from failing due to massive load. The symptoms of this would be a loss of availability
of some content from the network as well as some specific peers being unable to contact the network at all.
When a peer requests content from the network, that peer will be notified of the available peers with the desired content. If the content is no longer available from a peer, the requesting peer will be able to query other peers in the list. If no other peers are accessible, the peer will display an error message asking the user to try again later. If a
peer has lost its server connection, it will try to connect to the other peers in its list in sequence.
If a peer cannot establish a connection to any server, the user is informed and asked to try again
later.

A second category of error exists at the peer-to-peer level. It is possible that the
file received is not identical to the one that was originally entered into the
network. This could occur through networking errors or malicious activity on the
side of the peer sending the file. To guard against this problem, the receiving
peer can examine the received file to verify that the hash of the received
file matches the expected hash of the content. If the hash value is incorrect, the
receiving peer could retry the transmission from another peer. If no other peer is available,
it could retry transmission from the same peer. If the second transmission is also
faulty the receiving peer could display an error message to the user and ask them to try
again later.

\section{Content Acquisition}

As mentioned in section \ref{sec:architecture}, one of the `hard' problems of peer-to-peer systems that
we attempted to address with our design is that of discovering content in the network. Content
discovery is facilitated using control servers. When a peer wishes to download a file from the
system, it will request a list of peers from a control server. It will then use this list to
retrieve content directly from another peer. To increase transfer speed, a peer can download
different chunks of the file from various peers simultaneously. The peer will favour faster connections
for larger download chunks.

The process of uploading a file also involves communication with a control server. To upload a file,
the peer must provide information about that file, including its name, intended location in the
distributed folder structure, and the hash of the file. The control server will perform some actions
once it receives the information. It will inform all other control servers of the change in state.
Each server will, in turn, inform each of its connected peers of the change in information.
The original control server will also inform the peer that performed the upload to push the content to
some number of other peers in the network. The push to other peers is performed to ensure
that there is more than one source for the content in the network, but the content is not guaranteed
to be pushed to more than one other peer. In this sense, our design uses a lazy-replication scheme
for content in the network.

\section{Design Limitations}

There are two major limitations in our design, both stemming from the environmental
assumptions that we made in section \ref{sec:overview}. The first assumption was
that the system would be deployed in a corporate or institutional environment of
limited size. Since we did not expect to support a network of very large size,
or design will have difficulty scaling beyond a certain size. This is because
of the synchronous update mechanism used to ensure all the servers are always
fully synchronized with one another. The larger the system becomes, the more
control servers will be required to handle to load from peers. As more peers
perform actions, the changes to server state will become more frequent. This will
mean that synchronization must happen between servers more frequently. Since
there are more servers, each synchronization action will take longer. It is easy
to imagine increasing the number of servers and peers such that the system cannot
finish one synchronization before it has to begin another and enters a state of
thrashing. One way this problem could possibly be reduced would be to relax the
constraint that all servers must always be perfectly synchronized with one another.
If synchronization were allowed to use a method of lazy replication, it would be
possible that more servers would be available more of the time to service requests
because they do not have to wait for all other servers to finish synchronizing. This
change would come at increased cost of complexity to the design in terms of how
to manage conflicts of state and also lead to the possibility of files disappearing
from the system completely if a server dies.

The second limitation is related to the first, but stems more directly from the
second assumption we made in our design. This assumption was that the network would
be mostly stable. This means that peers would remain connected to network most of the
time and that files would generally not be quickly added and removed from the system.
An extreme violation of this assumption would cause a degradation
in the level of service of the system. There would be an increased volume of synchronization
traffic between the peers and it would be very possible that content could become inaccessible.
There is no clear adjustment to the design that could avoid this problem.

\section{Our Prototype Implementation}

We have implemented a simple prototype of our design. The following subsections describe
that prototype.

\subsection{What we've implemented}

We decided to use Java and Java's Remote Method Invocation (RMI) to implement our prototype
distributed file system. We chose Java and RMI because these two technologies greatly simplify
the implementation process by abstracting away many of the networking details required for
communication between the different elements of our system.

Our prototype involves only two control servers (primary and secondary). All peers in the system
will be connected to only one of the two servers at a time. The prototype implementation does not use any
of the load-balancing potential of having more than one control server, but rather uses the second server
only as a backup in case the first server fails. The location of the two servers is provided statically
to peers and servers using a configuration file. Each peer will attempt to connect to the primary server, and only if the
primary server is down will they attempt to connect to the secondary server. Each server maintains a connection
to the other. The primary server informs the secondary server of all state changes as they happen so
that no state information is lost if the primary server crashes. The secondary server maintains a connection
to the primary server to determine if the primary server goes down and it needs to take over
coordination activities. If the primary server fails, peers will lose their connection to the primary
server and connect to the secondary server. When the secondary server receives a service request,
it checks to see if the primary server is active. If the primary server is active, the secondary
server will respond to a service request from a peer with a "I am not the primary server" exception.
If the secondary server receives a request and determines that the primary server is dead, it will
happily process that request. When the Primary server recovers after a period of outage, it will first
connect to the secondary server and request the current state of the network. This will signal to
the secondary server that the primary server is back up and the secondary server will notify
all peers that the primary server is back and refuse to service any further peer requests.
When this happens, the peers will automatically reconnect to the primary server.
A representation of the network created by our prototype implementation is presented in figure \ref{fig:reality}.

\begin{figure}
  \begin{centering}
  \includegraphics[width=1.0\textwidth]{reality.png}
  \caption{Network Architecture of Prototype Implementation.}
  \label{fig:reality}
  \end{centering}
\end{figure}


When a peer first connects to a server, the peer informs the server of the files it has in its local content
store. When a peer requests for a specific file through the GUI, the server will inform the requesting
peer of all the available peers with the file. The peer will download the file from one
of the peers in the list. If an error occurs, the peer will try to retrieve the file from another peer. When the peer
downloads a file from the network, the peer can specify where the file should be saved on the local system. At the
same time, the file is saved in the working directory (defined by the configuration file) using the hash as the file name.

The peer may add files to and remove files from the network by informing the server. The peer
may also make changes to the directory structure of the distributed file system.
When the file system state changes, the server will
push the information to the connecting peers; thus the information presented to a peer is current.

\subsection{Limitations}

Our implementation successfully demonstrates the major concepts of our design, but it is a
proof-of-concept prototype; therefore, not all the desired functionality is present. The following list
presents the ways that our implementation falls short of our design:

\begin{itemize}
\item \textit{All-or-Nothing Data Transfer}\\
Currently, when a client downloads a file from a peer, it is not appropriately broken up into chunks. If the client does not have
enough space to handle the transfer, the download operation will not work.

\item \textit{Download is a blocking operation}\\
Downloading is a blocking operation
and the graphical user interface will hang until the request is completed or an error is encountered.

\item \textit{No Load Balancing}\\
The prototype uses the pair of servers solely to implement failover
functionality. There is no consideration of load balancing between
the two servers in our prototype implementation.

\item \textit{Expensive Failover}\\
Because our prototype implementation specifies that only one of the two servers
may be servicing peers at any time, the network must be rebuilt each time
a server fails or recovers. Each peer has to individually reconnect
to the appropriate server. This will mean that each server failure will
be accompanied by a brief period of inactivity in the network.

\item \textit{An identical file may only be added once}\\
Only one copy of file with the same contents, yielding an identical hash,
to any other file may exist in the system at any time.

\item \textit{Macroscopic state updates}\\
Changes to the directory structure of the distributed file system are
pushed in a macroscopic way to both peers and servers. Instead of simply passing
the parent element of the changed subtree, the entire tree is always passed.

\item \textit{Badly maintained local content store}\\
There are no size limitations on the local content store. Content is not removed
from the local content store when it is removed from the network. These
two conditions could eventually lead to filling the user's hard drive.

\item \textit{No Guarantee of Content Replication}\\
Our implementation does not actively attempt to replicate content on more than one peer.
Content is only replicated in the network by the activity of peers
downloading content because of user requests.

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% back matter (more Ewww :) )
\backmatter{}

%\bibliography{se2-design-bib}

\section{Acknowledgements}\label{sec:acknowledgements}
We would like to thank Mr. Simon Law for his uw-wkrpt \LaTeX{} classes
from which this document's formatting is derived. We would also like to thank
NeoEdge Networks Inc. for the inspiration for our design.

% if you want to use glosstex, you'll have to fudge with page numbers
% fudge with page numbers:
%\addtocontents{toc}{\protect\contentsline{section}{Glossary}{19}}
% proper way:
% \addcontentsline{toc}{section}{Glossary}
% do the glossary
%\printglosstex(glo)

%\section{Glossary}\label{sec:glossary}
%Some glossary here

% cue the fat lady
\end{document}

